#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    struct cmp {
        bool operator()(ListNode* l1, ListNode* l2) {
            return l1->val > l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        ListNode* head = new ListNode;
        ListNode* tmp = head;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i])
                pq.push(lists[i]);
        }
        while (!pq.empty()) {
            ListNode* top = pq.top();
            pq.pop();
            if (top->next)
                pq.push(top->next);
            tmp->next = top;
            tmp = tmp->next;
        }
        tmp = head->next;
        return tmp;
    }
};